import java.util.ArrayList;


public class BuildPath implements GlobalSettings{

	int dist[][]=new int[trees.size()][trees.size()];
	int next[][]=new int[trees.size()][trees.size()];
	
	void findPath()
	{
		
		if(connectedMatrix[0][trees.size()-1]!=-1)
		{
			startPathPoints.add(startConnectTreePoints.get(connectedMatrix[0][trees.size()-1]));
			endPathPoints.add(endConnectTreePoints.get(connectedMatrix[0][trees.size()-1]));
			System.out.println(startConnectTreePoints.get(connectedMatrix[0][trees.size()-1]));
			System.out.println("end:"+endConnectTreePoints.get(connectedMatrix[0][trees.size()-1]));
		}
		else
		{
			//initialize hop distances
			for(int i=0;i<trees.size();i++)
				for(int j=0;j<trees.size();j++)
					if(connectedMatrix[i][j]==-1)
					{
						if(i==j)							
							dist[i][j]=0;
						else
							dist[i][j]=999;
					}						
					else
						dist[i][j]=1;
			
			for(int k=0;k<trees.size();k++)
				for(int i=0;i<trees.size();i++)
					for(int j=0;j<trees.size();j++)
						if(dist[i][k] + dist[k][j] < dist[i][j])
						{
							dist[i][j]=dist[i][k] + dist[k][j];
							next[i][j]=k;
						}
			String nodeList=new String();
			nodeList=Path(0,trees.size()-1);
			System.out.println("Shortest Path:"+nodeList);
			String[] nodes=nodeList.split(",");
			for(int i=1;i<nodes.length;i++)
				System.out.println(nodes[i]);
		//	startPathPoints.add(startPoint);
			startPathPoints.add(startConnectTreePoints.get(connectedMatrix[0][Integer.parseInt(nodes[1])]));
			endPathPoints.add(endConnectTreePoints.get(connectedMatrix[0][Integer.parseInt(nodes[1])]));
			int k=Integer.parseInt(nodes[1]);
			for(int i=2;i<nodes.length;i++)
			{
				startPathPoints.add(startConnectTreePoints.get(connectedMatrix[k][Integer.parseInt(nodes[i])]));
				endPathPoints.add(endConnectTreePoints.get(connectedMatrix[k][Integer.parseInt(nodes[i])]));
				k=Integer.parseInt(nodes[i]);
			}
			startPathPoints.add(startConnectTreePoints.get(connectedMatrix[Integer.parseInt(nodes[nodes.length-1])][trees.size()-1]));
			endPathPoints.add(endConnectTreePoints.get(connectedMatrix[Integer.parseInt(nodes[nodes.length-1])][trees.size()-1]));
			//endPathPoints.add(goalPoint);
		}
	}

	private String Path(int i, int j) {
		// TODO Auto-generated method stub
		if(dist[i][j]==999)
			return null;
		Integer inter=(Integer)next[i][j];
		String intermediate=inter.toString();
		if(inter==0)
			return "";
		else
			return Path(i,inter)+","+intermediate+","+Path(inter,j);
	}	
}
